//给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[
//b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
//
//
// 0 <= a, b, c, d < n
// a、b、c 和 d 互不相同
// nums[a] + nums[b] + nums[c] + nums[d] == target
//
//
// 你可以按 任意顺序 返回答案 。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,0,-1,0,-2,2], target = 0
//输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
//
//
// 示例 2：
//
//
//输入：nums = [2,2,2,2,2], target = 8
//输出：[[2,2,2,2]]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 200
// -10⁹ <= nums[i] <= 10⁹
// -10⁹ <= target <= 10⁹
//
//
// Related Topics 数组与矩阵 双指针 排序 👍 1578 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function fourSum(nums: number[], target: number): number[][] {

    nums.sort((a, b) => a - b);
    let first: number = 0,
        second: number,
        third: number,
        fourth: number;
    let length: number = nums.length;
    let resArr: number[][] = [];
    for (; first < length; first++) {
        if (first > 0 && nums[first] === nums[first - 1]) {
            continue;
        }
        for (second = first + 1; second < length; second++) {
            if ((second - first) > 1 && nums[second] === nums[second - 1]) {
                continue;
            }
            third = second + 1;
            fourth = length - 1;
            while (third < fourth) {
                let total: number = nums[first] + nums[second] + nums[third] + nums[fourth];
                if (total === target) {
                    resArr.push([nums[first], nums[second], nums[third], nums[fourth]]);
                    third++;
                    fourth--;
                    while (nums[third] === nums[third - 1]) third++;
                    while (nums[fourth] === nums[fourth + 1]) fourth--;
                } else if (total < target) {
                    third++;
                } else {
                    fourth--;
                }
            }
        }
    }
    return resArr;
//leetcode submit region begin(Prohibit modification and deletion)
}
